package com.wdc.回溯;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

@SuppressWarnings("all")
public class E04Leetcode39 {
    private List<List<Integer>> result = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtracking(candidates,target,0,0);
        return result;
    }
    void backtracking(int[] candidates , int target  ,int sum ,int startIndex){
        //结束递归条件
        //加入路径
        if (sum > target){
            return;
        }
        if (sum == target){
            result.add(new ArrayList<>(path));
            return;

        }


        //循环每一个数
        for (int i = startIndex; i < candidates.length; i++) {

            //求和
            sum += candidates[i];
            //剪枝
            if (sum > target){
                break;
            }
            //加入路径
            path.add(candidates[i]);
            //递归求深度
            backtracking(candidates,target,sum,i);
            //回溯
            sum -= candidates[i];

            path.removeLast();
        }

    }

    public static void main(String[] args) {
        int[] arr = {2,3,6,7};
        E04Leetcode39 e04Leetcode39 = new E04Leetcode39();
        System.out.println(e04Leetcode39.combinationSum(arr, 7));
    }


}
